package com.leetcode.algorithm.y22.m09.w3;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import com.leetcode.algorithm.common.TreeNode;

/**
 * 637. 二叉树的层平均值
 * 
 * https://leetcode.cn/problems/average-of-levels-in-binary-tree/
 * 
 * @author jie.deng
 *
 */
class Question0637Solution01 {

	public List<Double> averageOfLevels(TreeNode root) {
		List<Double> result = new ArrayList<>();
		// 广度优先搜索，使用队列实现，先进先出
		if (root == null) {
			return result;
		}
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.offer(root);
		while (!queue.isEmpty()) {
			long sum = 0;
			// 当前层次结点个数
			int size = queue.size();
			// 遍历当前层
			for (int i = 0; i < size; i++) {
				TreeNode node = queue.poll();
				// 遍历当前结点
				sum += node.val;
				if (node.left != null) {
					queue.offer(node.left);
				}
				if (node.right != null) {
					queue.offer(node.right);
				}
			}
			result.add((double) sum / size);
		}
		return result;
	}

}